Definition

The class REG⁡(Σ)\operatorname{REG}(\Sigma) of regular languages is the smallest class (i.e. set of) languages (for alphabet Σ\Sigma) such that

  • ∅∈REG⁡(Σ)\emptyset \in \operatorname{REG}(\Sigma) and {a}∈REG⁡(Σ)\{a\} \in \operatorname{REG}(\Sigma) for every a∈Σa \in \Sigma
  • if L,M∈REG⁡(Σ)L,M \in \operatorname{REG}(\Sigma) then L∪M∈REG⁡(Σ)L \cup M \in \operatorname{REG}(\Sigma) (union), L⋅M∈REG⁡(Σ)L \cdot M \in \operatorname{REG}(\Sigma) (concatenation), and L∗∈REG⁡(Σ)L^* \in \operatorname{REG}(\Sigma) (Kleene star)

Notes

  • every finite language is regular

See also

References

  1. M. Avanzini, Lecture Notes, Topic: “finite automata.” M1-AL, Centre Inria d’Université Côte d’Azur, 2021. <https://www-sop.inria.fr/members/Martin.Avanzini/teaching/2021/AL/slides/w1.pdf
  2. https://en.wikipedia.org/wiki/Regular_language
  3. https://www.cs.hunter.cuny.edu/~sweiss/course_materials/csci265/KleenesTheorem.pdf